import java.util.ArrayList;
import java.util.HashSet;
import java.util.TreeMap;
import java.util.TreeSet;

/**
 * vstup vlastni cfg
 * @author Zuzana Krejcova
 */
public abstract class GreibachoveNF
{
    public static Gramatika transformuj(Gramatika g)
    {
        return prevedDoGNF(odstranLevouRekurzi(g));
    }

    public static Gramatika prevedDoGNF(Gramatika g)
    {
        TreeSet<String> pomTS = new TreeSet(new ComparatorNetermu(g));
        pomTS.addAll(g.neterminaly);
        ArrayList<String> razeneNetermy = new ArrayList(pomTS);
        TreeMap<String, HashSet<ArrayList<String>>> novaPravidla = new TreeMap();
        TreeSet<String> noveNetermy = new TreeSet(g.neterminaly);

        String neterm = razeneNetermy.get(razeneNetermy.size()-1);
        HashSet<ArrayList<String>> pravaStrana = new HashSet();//g.pravidla.get(neterm);
        for (ArrayList<String> al : g.pravidla.get(neterm))
        {
            ArrayList<String> al2 = new ArrayList();
            al2.addAll(al);
            pravaStrana.add(al2);
        }
        novaPravidla.put(neterm, pravaStrana);
        for (int i = razeneNetermy.size()-2; i>=0; i--)
        {
            neterm = razeneNetermy.get(i);
            pravaStrana = new HashSet();
            for (ArrayList<String> al : g.pravidla.get(neterm))
            {
                ArrayList<String> al2 = new ArrayList();
                al2.addAll(al);
                pravaStrana.add(al2);
            }
            if (pravaStrana != null)
            {
                novaPravidla.put(neterm, new HashSet());
                for (ArrayList<String> pravidlo : pravaStrana)
                {
                    if (razeneNetermy.subList(i+1,razeneNetermy.size()).contains(pravidlo.get(0)))
                    {
                        //substituce
                        for (ArrayList<String> pravidloSub : g.pravidla.get(pravidlo.get(0)))
                        {
                            ArrayList<String> pomPravidlo = new ArrayList();
                            pomPravidlo.addAll(pravidloSub);
                            pomPravidlo.addAll(pravidlo.subList(1, pravidlo.size()));
                            novaPravidla.get(neterm).add(pomPravidlo);
                        }
                    } else
                    {
                        novaPravidla.get(neterm).add(pravidlo);
                    }
                }
            }
        }
        TreeMap<String, HashSet<ArrayList<String>>> pomPravidla = new TreeMap();
        for (String neterm2 : novaPravidla.keySet()) //projdi kazdy radek
        {
            for (ArrayList<String> pravidlo : novaPravidla.get(neterm2)) //na nem kazde pravidlo
            {
                for (int i=1; i<pravidlo.size(); i++) // a v nem kazdy symbol
                {
                    if (g.terminaly.contains(pravidlo.get(i))) // pokud je cokoli krom 1. term
                    { // nahrad to netermem a pridej pravidlo a neterm
                        String novyNeterm = "<"+pravidlo.get(i)+">";
                        pravaStrana = new HashSet();
                        ArrayList<String> pomPravidlo = new ArrayList();
                        pomPravidlo.add(pravidlo.get(i));
                        pravaStrana.add(pomPravidlo);
                        noveNetermy.add(novyNeterm);
                        pomPravidla.put(novyNeterm, pravaStrana);

                        pravidlo.set(i, novyNeterm);
                    }
                }
            }
        }
        novaPravidla.putAll(pomPravidla);
        Gramatika ret = new Gramatika(noveNetermy, new TreeSet(g.terminaly), g.koren, novaPravidla);
        return ret;
    }



    public static Gramatika odstranLevouRekurzi(Gramatika g)
    {
        TreeSet<String> netermy = new TreeSet(g.neterminaly);
        TreeMap<String, HashSet<ArrayList<String>>> novaPravidla = new TreeMap();
        ArrayList<String> razeneNetermy = new ArrayList(g.neterminaly);
        String neterm;

        for (int i=0; i<razeneNetermy.size(); i++)
        {
            HashSet<ArrayList<String>> pravaStrana = new HashSet();
            HashSet<ArrayList<String>> pravaStrana2;
            ArrayList<String> pr;
            String novyNeterm;
            neterm = razeneNetermy.get(i);
            novaPravidla.put(neterm, new HashSet());
            if (g.pravidla.get(neterm)!=null) //existuje pravidlo pro ten neterm?
            {
                pravaStrana.addAll(g.pravidla.get(neterm));
                for (ArrayList<String> pravidlo : pravaStrana) //projdi kazde pravidlo
                {
                    pr = new ArrayList();
                    pr.addAll(pravidlo);
                    for (int j=0; j<i; j++) // odstran levorekurzivni smycky
                    {
                        ArrayList<String> pr2 = new ArrayList();
                        pravaStrana2 = new HashSet();
                        for (ArrayList<String> al:novaPravidla.get(razeneNetermy.get(j)))
                        {
                            pr2.addAll(al);
                            pravaStrana2.add(pr2);
                            pr2 = new ArrayList();
                        }
                        if (pravidlo.get(0).equals(razeneNetermy.get(j))) // zkontroluj, jak zacina
                        {
                            pr.remove(0);
                            for (ArrayList<String> pravidloSub : pravaStrana2)
                            {
                                pravidloSub.addAll(pr); // substituuj a odstran
                                novaPravidla.get(neterm).add(pravidloSub);
                            }
                        }
                    }
                    if (!razeneNetermy.subList(0, i).contains(pravidlo.get(0))) // pokud pravidlo nezacina nicim proslym
                        novaPravidla.get(neterm).add(pr);
                    // kdyz uz tam pravidlo mam bez levorekurzivni smycky, odstranim primou levou rekurzi
                }

                pravaStrana = new HashSet();
                pravaStrana2 = new HashSet();
                novyNeterm = neterm+"'";
                if (netermy.contains(novyNeterm))
                    do
                    {
                        novyNeterm += "'";
                    } while (netermy.contains(novyNeterm));
                netermy.add(novyNeterm); // smazat, pokud nebude pouzit

                for (ArrayList<String> pravidlo : novaPravidla.get(neterm)) //projdi pravidla, rozdel rekurzivni a nerekurzivni
                {
                    pr = new ArrayList();
                    if (pravidlo.get(0).equals(neterm)) //rekurzivni
                    {
                        pravidlo.remove(0); //oddelej problematicky prvni znak
                        pravaStrana.add(pravidlo);
                        pr.addAll(pravidlo);
                        pr.add(novyNeterm);
                        pravaStrana.add(pr);
                    } else                              //nerekurzivni
                    {
                        pravaStrana2.add(pravidlo);
                        pr.addAll(pravidlo);
                        pr.add(novyNeterm);
                        pravaStrana2.add(pr);
                    }
                }
                if (!pravaStrana.isEmpty())
                {
                    //novaPravidla.get(neterm).removeAll(pravaStrana);
                    for (ArrayList<String> al:pravaStrana)
                    {
                        if (obsahuje(novaPravidla.get(neterm),al))
                        {
                            novaPravidla.get(neterm).clear();
                            novaPravidla.get(neterm).addAll(odstranPravidlo(novaPravidla.get(neterm),al));
                        }
                    }
                    novaPravidla.get(neterm).addAll(pravaStrana2);
                    novaPravidla.put(novyNeterm, pravaStrana);
                } else
                {
                    netermy.remove(novyNeterm);
                }
            }
        }
        TreeMap<String, HashSet<ArrayList<String>>> pomPravidla = new TreeMap(novaPravidla); //mazani prazdnych pravidel
        for (String klic : pomPravidla.keySet())
        {
            if (pomPravidla.get(klic).isEmpty()) novaPravidla.remove(klic);
        }
        Gramatika ret = new Gramatika(netermy,new TreeSet(g.terminaly),g.koren,novaPravidla);
        return ret;
    }

    private static boolean obsahuje(HashSet<ArrayList<String>> pravaStrana, ArrayList<String> pravidlo)
    {
        for (ArrayList<String> al:pravaStrana)
        {
            if (al.toString().equals(pravidlo.toString()))
                return true;
        }
        return false;
    }

    private static HashSet<ArrayList<String>> odstranPravidlo(HashSet<ArrayList<String>> pravaStrana, ArrayList<String> pravidlo)
    {
        HashSet<ArrayList<String>> ret = new HashSet();
        for (ArrayList<String> al:pravaStrana)
        {
            if (!al.toString().equals(pravidlo.toString()))
                ret.add(al);
        }
        return ret;
    }
}
